package com.ywk.base.dataStructure.sparsearray;

import java.io.*;
/*稀疏数组（压缩二维数组，只保留索引上有目标值的位置）*/
public class SparseArray {
	public static void main(String[] args) {
		int[][] chess=new int[11][11];
		chess[1][2]=1;
		chess[2][3]=2;
		chess[5][5]=2;
		chess[9][8]=1;
		System.out.println("原数组：");
		for (int[] row: chess) {
			for(int data: row) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		//将二维数组转换稀疏数组
		//遍历二维数组计算非零数的个数
		int sum=0;//非零数的个数
		for(int i=0;i<chess.length;i++) {
			for(int j=0;j<chess[i].length;j++) {
				if(chess[i][j]!=0) {
					sum++;
				}
			}
		}
		//创建稀疏数组
		int[][] sparse=new int[sum+1][3];
		sparse[0][0]=11;
		sparse[0][1]=11;
		sparse[0][2]=sum;
		int count=0;//稀疏数组的行数
		for(int i=0;i<chess.length;i++) {
			for(int j=0;j<chess[i].length;j++) {
				if(chess[i][j]!=0) {
					count++;
					sparse[count][0]=i;
					sparse[count][1]=j;
					sparse[count][2]=chess[i][j];
				}
			}
		}
		File file=new File("D:\\Work\\myProject\\dataStructureAndAlgorithm\\out\\sparse.txt");
		FileWriter fw=null;
		try {
			fw=new FileWriter(file);
			for (int i = 0; i < sparse.length; i++) {
				for (int j = 0; j < sparse[i].length; j++) {
					fw.write(sparse[i][j]+""+"\t");
				}
				fw.write("\n");
			}
		} catch (IOException e) { 
			System.out.println("IO异常");
		}finally {
			try {
				fw.close();
			} catch (IOException e) {
				System.out.println("IO异常");
			}
		}
		
		System.out.println();
		System.out.println("稀疏数组：");
		for (int[] row : sparse) {
			for (int data : row) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		
		//恢复后的数组
		FileReader fr=null;
		BufferedReader br=null;
		int[][] chess1=new int[sum+1][3];
		try {
			fr=new FileReader(file);
			br=new BufferedReader(fr);
			String line;
			int row=0;
			while((line =br.readLine())!=null) {
//				System.out.println(line);
				String[] temp=line.split("\t");//将字符串分割成字符数组
//				for (int i = 0; i < temp.length; i++) {
//					System.out.print(temp[i]);
//				}
				for (int i = 0; i < temp.length; i++) {
					chess1[row][i]=Integer.parseInt(temp[i]);
				}
				row++;
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}catch (IOException e) {
		}finally {
			try {
				fr.close();
				br.close();
			} catch (IOException e) {
			}
		}
		
//		int[][] chess1=new int[sparse[0][0]][sparse[0][1]];
//		for(int i=1;i<=sparse[0][2];i++) {
//			chess1[sparse[i][0]][sparse[i][1]]=sparse[i][2];
//		}
		System.out.println();
		System.out.println("回复后的数组：");
		for (int[] row : chess1) {
			for (int data : row) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
	}
}
